package com.datastructures2.unionFind;

/**
 * @author MaoLin Wang
 * @date 2020/4/1119:50
 */
public class UF {
   private int id[];
   private int weighted[];
   private int count;

    public UF(int count) {
        this.count = count;
        this.id=new int[count];
        weighted=new int[count];
        for (int i = 0; i < count; i++) {
            id[i]=i;
            weighted[i]=1;
        }
    }
    public void union(int p,int q){
        if (checkIndex(p)&&checkIndex(q)){
            int i = find(p);
            int j = find(q);
            if (i==j){
                return;
            }else {
                if (weighted[i]<weighted[j]){
                    id[i]=j;
                    weighted[j] += weighted[i];
                }else {
                    id[j]=i;
                    weighted[i] += weighted[j];
                }
            }
            count--;
        }
    }
    private boolean WeightedBigTo(int i, int j){
        return weighted[i]>weighted[j];
    }

    private boolean checkIndex(int i){
        if (i<0||i>=id.length){
            return false;
        }
        return true;
    }
    public boolean connected(int i,int j){
        return find(i)==find(j);
    }
    private int find(int p){
        if (p>=0 && p<id.length){
            int root=p;
            while (root!=id[root]){
                root=id[root];
            }

            while (id[p]!=root){
                int temp=p;
                id[temp]=root;
                p=id[p];
            }
            return root;
        }
        return -1;


    }

    public static void main(String[] args) {
        UF unionFind = new UF(10);
        unionFind.union(4,3);
        unionFind.union(3,8);
        unionFind.union(6,5);
        unionFind.union(9,4);
        unionFind.union(2,1);
        unionFind.union(8,9);
        unionFind.union(5,0);
        unionFind.union(7,2);
        unionFind.union(6,1);
        unionFind.union(1,0);
        unionFind.union(6,7);
        int[] id = unionFind.id;
        for (int i = 0; i < id.length; i++) {
            System.out.println("id["+i+"]:"+id[i]);
        }

    }
}
